package main

import "strings"

func wordBreak(s string, wordDict []string) bool {
	dp := make([]bool, len(s)+1) // dp[i]==true => s[:i] 可以被拼出来
	dp[0] = true
	for i, t := range dp {
		if !t {
			continue
		}
		for _, word := range wordDict {
			if strings.HasPrefix(s[i:], word) {
				dp[i+len(word)] = true
			}
		}
	}
	return dp[len(s)]
}

func main() {
	println(wordBreak("cars", []string{"car", "ca", "rs"}))
	//println(wordBreak("wc", []string{"w", "c"}))
	println(wordBreak("leetcode", []string{"leet", "code"}))
	println(wordBreak("applepenapple", []string{"apple", "pen"}))
	println(wordBreak("catsandog", []string{"cats", "dog", "sand", "and", "cat"}))
}
